'''
给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。

输入：
"XDOYEZODEYXNZ","XYZ"
返回值：
"YXNZ"
'''

'''
用两个下标来寻找，left,right
固定left不动，right不断+1往右移动，遇到给定字符就给对应字符的字典value+1， 
当left到right之间包含了所有的 给定字符 时，固定right不动，
开始向右移动left，
left遇到 给定字符 就计算此时到right之间的长度，并给对应字符的字典value-1，
当对应字符的字典value为0时，开始移动right，往右寻找该字符，
当又找到了所有给定字符，
又继续移动left
'''

# 滑窗法（左右指针）
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict
        need = defaultdict(int)#将t变为哈希表
        for i in t:
            need[i] += 1  #记录t中的哈希表
        # 两个中间标志：min_len， needCnt
        min_len, res = float('inf'), ""
        l, needCnt = len(s), len(t)
        left = right = 0
        #------------------------------
        while right < l:#向右滑动窗口
            if need[s[right]] > 0:#如果s中的值满足t的字符
                needCnt -= 1# needCnt就减少
            '''
            need[s[right]] -= 1 其实也可以换成，+=1，
            -1是指用负数代表已经找到目标，
            +1是指用正数代表已经找目标
            '''
            need[s[right]] -= 1# 访问过的数都-1，主要去除不是t的元素，非t元素变成-1
            right += 1		# 向右滑动
            while needCnt == 0:	#当此时窗口包含所有t字符
                if min_len > right - left:#将最小间距赋值给res
                    min_len = right - left
                    res = s[left:right]
                if need[s[left]] == 0:#刚好满足t所有字符的左边字符被删除 # 非t元素为-1
                    needCnt += 1  # 所需要的字符的总数目加1
                need[s[left]] += 1 # 访问过的字符数目加1，可以防止字符数过多，导致负数超出了-2**32
                left += 1 # 移动左指针 # 不找齐目标不移动
        #-------------------------------------
        return res


s,t = "XDOYEZODEYXNZ56","XYZ"
so = Solution()
print(so.minWindow(s,t))











